{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Sorted Matrix Search LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #binary-search #divide-and-conquer #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #二分查找 #分治 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: searchMatrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #排序矩阵查找"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定M&times;N矩阵，每一行、每一列都按升序排列，请编写代码找出某元素。</p>\n",
    "\n",
    "<p><strong>示例:</strong></p>\n",
    "\n",
    "<p>现有矩阵 matrix 如下：</p>\n",
    "\n",
    "<pre>[\n",
    "  [1,   4,  7, 11, 15],\n",
    "  [2,   5,  8, 12, 19],\n",
    "  [3,   6,  9, 16, 22],\n",
    "  [10, 13, 14, 17, 24],\n",
    "  [18, 21, 23, 26, 30]\n",
    "]\n",
    "</pre>\n",
    "\n",
    "<p>给定 target&nbsp;=&nbsp;<code>5</code>，返回&nbsp;<code>true</code>。</p>\n",
    "\n",
    "<p>给定&nbsp;target&nbsp;=&nbsp;<code>20</code>，返回&nbsp;<code>false</code>。</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [sorted-matrix-search-lcci](https://leetcode.cn/problems/sorted-matrix-search-lcci/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [sorted-matrix-search-lcci](https://leetcode.cn/problems/sorted-matrix-search-lcci/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        m = len(matrix)\n",
    "        if m == 0:\n",
    "            return False\n",
    "        n = len(matrix[0])\n",
    "        if n == 0:\n",
    "            return False\n",
    "        x, y = 0, n - 1\n",
    "        while x < m and y >= 0:\n",
    "            if matrix[x][y] == target:\n",
    "                return True\n",
    "            elif target < matrix[x][y]:\n",
    "                y -= 1\n",
    "            else:\n",
    "                x += 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        if len(matrix) == 0 or len(matrix[0]) == 0:\n",
    "            return False\n",
    "        for row in matrix:\n",
    "            idx = bisect.bisect_left(row, target)\n",
    "            if idx < len(row) and row[idx] == target:\n",
    "                return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        if not len(matrix) or not len(matrix[0]): \n",
    "            return False\n",
    "        row = 0\n",
    "        col = len(matrix[0]) - 1\n",
    "        while row != len(matrix) and col != -1:\n",
    "            if matrix[row][col] > target:\n",
    "                col -= 1\n",
    "            elif matrix[row][col] < target:\n",
    "                row += 1   \n",
    "            else:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        if not len(matrix) or not len(matrix[0]): \n",
    "            return False\n",
    "        row = 0\n",
    "        col = len(matrix[0]) - 1\n",
    "        while row != len(matrix) and col != -1:\n",
    "            if matrix[row][col] > target:\n",
    "                col -= 1\n",
    "            elif matrix[row][col] < target:\n",
    "                row += 1   \n",
    "            else:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        new = []\n",
    "        for i in matrix:\n",
    "            new.extend(i)\n",
    "        if target in new:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        for i in range(len(matrix)):\n",
    "            for j in range(len(matrix[0])):\n",
    "                if target == (matrix[i][j]):\n",
    "                    return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        if not matrix:\n",
    "            return False\n",
    "\n",
    "        x, y = 0, len(matrix[0]) - 1\n",
    "\n",
    "        while x < len(matrix) and y >= 0:\n",
    "            if matrix[x][y] == target:\n",
    "                return True\n",
    "            elif matrix[x][y] < target:\n",
    "                x += 1\n",
    "            else:\n",
    "                y -= 1\n",
    "\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        if not matrix or (matrix and not matrix[0]):\n",
    "            return False\n",
    "        height = len(matrix)\n",
    "        width = len(matrix[0])\n",
    "        for i in range(height):\n",
    "            for j in range(width):\n",
    "                if matrix[i][0] > target:\n",
    "                    return False\n",
    "                if matrix[i][j] > target:\n",
    "                    break\n",
    "                if matrix[i][j] == target:\n",
    "                    return True\n",
    "\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        if len(matrix) == 0 or len(matrix[0]) == 0:\n",
    "            return False\n",
    "        row, col = 0, len(matrix[0])-1\n",
    "        while row < len(matrix) and col >= 0:\n",
    "            if matrix[row][col] == target:\n",
    "                return True\n",
    "            elif matrix[row][col] > target:\n",
    "                col -= 1\n",
    "            else:\n",
    "                row += 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        if len(matrix) == 0: return False\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "        x = 0\n",
    "        y = n-1\n",
    "        while x < m and y >= 0:\n",
    "            if matrix[x][y] == target:\n",
    "                return True\n",
    "            elif matrix[x][y] < target:\n",
    "                x += 1\n",
    "            else:\n",
    "                y -= 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        if len(matrix)==0: return False \n",
    "        m,n = len(matrix),len(matrix[0])\n",
    "        row,col = 0,n-1\n",
    "        while(row<m and col>=0):\n",
    "            if matrix[row][col]==target:\n",
    "                return True \n",
    "            if matrix[row][col]>target:\n",
    "                col-=1\n",
    "            else:\n",
    "                row+=1\n",
    "        return False \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        if not matrix:\n",
    "            return False\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        x, y = 0, n - 1\n",
    "        while x >= 0 and x < m and y >= 0 and y < n:\n",
    "            if matrix[x][y] == target:\n",
    "                return True\n",
    "            elif matrix[x][y] > target:\n",
    "                y -= 1\n",
    "            else:\n",
    "                x += 1\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        if len(matrix) == 0 or len(matrix[0]) == 0:\n",
    "            return False\n",
    "        nrow, ncol = len(matrix), len(matrix[0])\n",
    "        def inRange(row, col):\n",
    "            if row < 0 or row >= nrow or col < 0 or col >= ncol:\n",
    "                return False\n",
    "            return True\n",
    "\n",
    "        cr, cc = len(matrix)-1, 0\n",
    "        while inRange(cr, cc):\n",
    "            if matrix[cr][cc] == target:\n",
    "                return True\n",
    "            elif matrix[cr][cc] > target:\n",
    "                cr -= 1\n",
    "            else:\n",
    "                cc += 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        if len(matrix) == 0 or len(matrix[0]) == 0:\n",
    "            return False\n",
    "        for row in matrix:\n",
    "            for element in row:\n",
    "                if element == target:\n",
    "                    return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        if not len(matrix) or not len(matrix[0]):\n",
    "            return False\n",
    "        row = 0\n",
    "        col = len(matrix[0])-1\n",
    "        while row < len(matrix) and col >= 0:\n",
    "            if matrix[row][col] > target:\n",
    "                col -= 1\n",
    "            elif matrix[row][col] < target:\n",
    "                row += 1\n",
    "            else:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        for i in matrix:\n",
    "            for j in i:\n",
    "                if(j==target):\n",
    "                    return True\n",
    "        \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        if not len(matrix) or not len(matrix[0]):\n",
    "            return False\n",
    "        row = 0\n",
    "        col = len(matrix[0])-1\n",
    "        while row != len(matrix) and col != -1:\n",
    "            if matrix[row][col] > target:\n",
    "                col -= 1\n",
    "            elif matrix[row][col] < target:\n",
    "                row += 1\n",
    "            else:\n",
    "                return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        if len(matrix) == 0 or len(matrix[0]) == 0:\n",
    "            return False\n",
    "        for row in matrix:\n",
    "            for element in row:\n",
    "                if element == target:\n",
    "                    return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        for i in range(len(matrix)):\n",
    "            for j in range(len(matrix[0])):\n",
    "                if matrix[i][j] == target:\n",
    "                    return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        if matrix == []:\n",
    "            return False\n",
    "        m = len(matrix)    #行\n",
    "        n = len(matrix[0]) #列\n",
    "        #print(m)\n",
    "        for i in range(m):\n",
    "            left = 0\n",
    "            right = n - 1\n",
    "            mid = (right - left) // 2 + left\n",
    "            #print(\"i===============\" + str(i))\n",
    "            while left <= right:\n",
    "                #print(\"left=\" + str(left))\n",
    "                #print(\"right=\" + str(right))\n",
    "                #print(\"mid=\" + str(mid))\n",
    "                #print(matrix[i][mid])\n",
    "                if matrix[i][mid] == target:\n",
    "                    return True\n",
    "                elif matrix[i][mid] < target:\n",
    "                    left = mid + 1\n",
    "                    mid = (right - left) // 2 + left\n",
    "                else:\n",
    "                    right = mid - 1\n",
    "                    mid = (right - left) // 2 + left\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        if len(matrix) == 0 or len(matrix[0]) == 0:\n",
    "            return False\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        x, y = 0, n-1\n",
    "        while x < m and y >= 0:\n",
    "            if matrix[x][y] == target:\n",
    "                return True\n",
    "            elif matrix[x][y] > target:\n",
    "                y -= 1\n",
    "            else:\n",
    "                x += 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        if not len(matrix) or not len(matrix[0]):\n",
    "            return False\n",
    "        m,n = len(matrix),len(matrix[0])\n",
    "        i,j = m-1,0\n",
    "        while i >= 0 and j < n:\n",
    "            num = matrix[i][j]\n",
    "            if num == target:\n",
    "                return True\n",
    "            elif num > target:\n",
    "                i -= 1\n",
    "            else:\n",
    "                j += 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        for line in matrix:\n",
    "            if target in line:\n",
    "                return True\n",
    "        return False\n",
    "\n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        if len(matrix)==0 or len(matrix[0])==0:\n",
    "            return False\n",
    "        m,n=len(matrix),len(matrix[0])\n",
    "        x,y=0,n-1\n",
    "        while x<m and y>=0:\n",
    "            if matrix[x][y]==target:\n",
    "                return True\n",
    "            if matrix[x][y]>target:\n",
    "                y-=1\n",
    "            else:\n",
    "                x+=1\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        for line in matrix:\n",
    "            res = self.search(line, target)\n",
    "            if res is None:\n",
    "                continue \n",
    "            else:\n",
    "                return True \n",
    "        \n",
    "        return False \n",
    "    \n",
    "    def search(self, arr: List, target) -> bool:\n",
    "        left = 0\n",
    "        right = len(arr) - 1\n",
    "        while left <= right:\n",
    "            mid = (left+right) // 2 \n",
    "\n",
    "            if arr[mid] == target:\n",
    "                return mid\n",
    "            \n",
    "            if arr[mid] < target:\n",
    "                left = mid + 1 \n",
    "            else:\n",
    "                right = mid - 1\n",
    "        \n",
    "        return None \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        row, col = 0, 0\n",
    "        visited = [[0]*len(matrix[0]) for _ in range(len(matrix))]\n",
    "        while row >= 0 and row < len(matrix) and col >=0 and col < len(matrix[0]):\n",
    "          #  print(row, col, matrix[row][col], visited)\n",
    "            visited[row][col] = 1\n",
    "            if matrix[row][col] == target:\n",
    "                return True\n",
    "            elif matrix[row][col] < target:\n",
    "                if col + 1 < len(matrix[0]) and visited[row][col+1] == 0:\n",
    "                    col += 1\n",
    "                else:\n",
    "                    row += 1\n",
    "            else:\n",
    "                col -= 1\n",
    "       # print(row, col, matrix[row][col], visited)\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        if not matrix:return False\n",
    "        m,n = len(matrix),len(matrix[0])\n",
    "        l,r = 0,n-1\n",
    "        while l<m and r>=0:\n",
    "            if matrix[l][r]<target:\n",
    "                l+=1\n",
    "            elif matrix[l][r]>target:\n",
    "                r-=1\n",
    "            else:\n",
    "                return True\n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        if not matrix:\n",
    "            return False\n",
    "        right = len(matrix[0])-1\n",
    "        left = 0\n",
    "        # [[1,1]]\n",
    "\n",
    "        while 0<=left<len(matrix) and 0<=right <=len(matrix[0])-1:\n",
    "            if matrix[left][right] == target:\n",
    "                return True\n",
    "            \n",
    "            if matrix[left][right]>target:\n",
    "                right-=1\n",
    "            \n",
    "            else:\n",
    "                left +=1\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        if not matrix:\n",
    "            return False\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if matrix[i][j] == target:\n",
    "                    return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        if len(matrix)==0 or len(matrix[0])==0:\n",
    "            return False\n",
    "        for row in matrix:\n",
    "            idx=bisect.bisect_left(row,target)\n",
    "            if idx<len(row) and row[idx]==target:\n",
    "                return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        if not len(matrix) or not len(matrix[0]):\n",
    "            return False\n",
    "        row = 0\n",
    "        col = len(matrix[0])-1\n",
    "        while row != len(matrix) and col != -1:\n",
    "            if matrix[row][col] > target:\n",
    "                col -= 1\n",
    "            elif matrix[row][col] < target:\n",
    "                row += 1\n",
    "            else:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        if len(matrix) == 0 or len(matrix[0]) == 0:\n",
    "            return False\n",
    "        for row in matrix:\n",
    "            if row[0] > target:\n",
    "                break\n",
    "            if row[bisect.bisect_right(row, target) - 1] == target:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        if not matrix:\n",
    "            return False\n",
    "        m,n=len(matrix),len(matrix[0])\n",
    "\n",
    "        if n==0:\n",
    "            return False\n",
    "\n",
    "        for i in range(m):\n",
    "            index = bisect_left(matrix[i],target)\n",
    "            if index!=n and matrix[i][index]==target:\n",
    "                return True\n",
    "\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        for line in matrix:\n",
    "            if line:\n",
    "                if line[0] <= target <= line[-1]:\n",
    "                    res = self.search(line, target)\n",
    "                    if res is None:\n",
    "                        continue \n",
    "                    else:\n",
    "                        return True \n",
    "        \n",
    "        return False \n",
    "    \n",
    "    def search(self, arr: List, target) -> bool:\n",
    "        left = 0\n",
    "        right = len(arr) - 1\n",
    "        while left <= right:\n",
    "            mid = (left+right) // 2 \n",
    "\n",
    "            if arr[mid] == target:\n",
    "                return mid\n",
    "            \n",
    "            if arr[mid] < target:\n",
    "                left = mid + 1 \n",
    "            else:\n",
    "                right = mid - 1\n",
    "        \n",
    "        return None \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        if len(matrix)==0 or len(matrix[0])==0:\n",
    "            return False\n",
    "        m,n=len(matrix),len(matrix[0])\n",
    "        x,y=0,n-1\n",
    "        while x<m and y>=0:\n",
    "            if matrix[x][y]==target:\n",
    "                return True\n",
    "            elif matrix[x][y]>target:\n",
    "                y-=1\n",
    "            else:\n",
    "                x+=1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        if len(matrix) == 0 or len(matrix[0]) == 0:\n",
    "            return False\n",
    "        for row in matrix:\n",
    "            if row[0] <= target and row[-1] >= target:\n",
    "                l, r = 0, len(row)-1\n",
    "                while l <= r:\n",
    "                    mid = (l + r) // 2\n",
    "                    if row[mid] < target:\n",
    "                        l = mid + 1\n",
    "                    elif row[mid] > target:\n",
    "                        r = mid - 1\n",
    "                    else:\n",
    "                        return True\n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        if len(matrix)==0 or len(matrix[0])==0:return False\n",
    "        m,n = len(matrix),len(matrix[0])\n",
    "        l,r = 0,n-1\n",
    "        while l<m and r>=0:\n",
    "            if matrix[l][r]<target:\n",
    "                l+=1\n",
    "            elif matrix[l][r]>target:\n",
    "                r-=1\n",
    "            else:\n",
    "                return True\n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        if not matrix:\n",
    "            return False\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        x, y = 0, n-1\n",
    "        while x < m and y > -1:\n",
    "            if matrix[x][y] == target:\n",
    "                return True\n",
    "            elif matrix[x][y] > target:\n",
    "                y -= 1\n",
    "            else:\n",
    "                x += 1\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        if not matrix:\n",
    "            return False\n",
    "        n, m = len(matrix), len(matrix[0])\n",
    "        for i in range(n):\n",
    "            idx = bisect_left(matrix[i], target)\n",
    "            if idx < m and target == matrix[i][idx]:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        '''for row in matrix:\n",
    "            for num in row:\n",
    "                if num == target:\n",
    "                    return True\n",
    "        return False\n",
    "        '''\n",
    "        if not matrix or not matrix[0]:\n",
    "            return False\n",
    "        for row in matrix:\n",
    "            idx = bisect.bisect_left(row, target)\n",
    "            if idx < len(row) and row[idx] == target:\n",
    "                return True\n",
    "        return False\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        if len(matrix) == 0:\n",
    "            return False\n",
    "        m, n = len(matrix),len(matrix[0])\n",
    "        mi, ni = m-1, 0\n",
    "        while (mi >= 0 and ni <= n-1):\n",
    "            if matrix[mi][ni] > target:\n",
    "                mi -= 1\n",
    "            elif matrix[mi][ni] < target:\n",
    "                ni += 1\n",
    "            else:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        if len(matrix)==0 or len(matrix[0])==0:\n",
    "            return False\n",
    "        for row in matrix:\n",
    "            idx=bisect.bisect_left(row,target)\n",
    "            if idx<len(row) and row[idx]==target:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        if matrix == []:\n",
    "            return False\n",
    "        m = len(matrix)    #行\n",
    "        n = len(matrix[0]) #列\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if matrix[i][j] == target:\n",
    "                    return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        if not matrix:\n",
    "            return False\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "        i, j = m-1, 0\n",
    "        while i >= 0 and j < n:\n",
    "            if matrix[i][j] == target:\n",
    "                return True\n",
    "            elif matrix[i][j] > target:\n",
    "                i -= 1\n",
    "            else:\n",
    "                j += 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        if len(matrix) == 0:\n",
    "            return False\n",
    "        col_len = len(matrix[0])\n",
    "        if col_len == 0:\n",
    "            return False\n",
    "        for row in matrix:\n",
    "            if row[0] > target:\n",
    "                break\n",
    "            idx = bisect.bisect_left(row, target)\n",
    "            if idx < col_len and row[idx] == target:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        if len(matrix) == 0 or len(matrix[0]) == 0:\n",
    "            return False\n",
    "        for row in matrix:\n",
    "            idx = bisect.bisect_left(row, target)\n",
    "            if idx < len(row) and row[idx] == target:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        # 二分 -- 右上角\n",
    "        m = len(matrix)\n",
    "\n",
    "        if not m :\n",
    "            return False\n",
    "        n = len(matrix[0])\n",
    "        if not n:\n",
    "            return False\n",
    "        row = 0\n",
    "        col = n - 1\n",
    "        while row != m and col != -1:\n",
    "            if matrix[row][col]> target:\n",
    "                col -= 1\n",
    "            elif matrix[row][col]<target:\n",
    "                row += 1\n",
    "            else:\n",
    "                return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        for r in range(len(matrix)):\n",
    "            row = matrix[r]\n",
    "            print(row)\n",
    "            l, r = 0, len(row)-1\n",
    "            while l<=r:\n",
    "                mid=(l+r)//2\n",
    "                if row[mid]==target:\n",
    "                    return True\n",
    "                if row[mid]<target:\n",
    "                    l=mid+1\n",
    "                else:\n",
    "                    r=mid-1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        if len(matrix) == 0 or len(matrix[0]) == 0:\n",
    "            return False\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        x, y = 0, n - 1\n",
    "        while x < m and y >= 0:\n",
    "            if matrix[x][y] == target:\n",
    "                return True\n",
    "            if matrix[x][y] > target:\n",
    "                y -= 1\n",
    "            else:\n",
    "                x += 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        if len(matrix) == 0 or len(matrix[0]) == 0:\n",
    "            return False\n",
    "        m, n = len(matrix), len(matrix[0]) # n有可能不存在，要放判断后面\n",
    "        x, y = 0, n-1\n",
    "        while x < m and y >= 0:\n",
    "            if matrix[x][y] == target:\n",
    "                return True\n",
    "            elif matrix[x][y] > target:\n",
    "                y -= 1\n",
    "            else:\n",
    "                x += 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        if len(matrix)==0 or len(matrix[0])==0:return False\n",
    "        m,n = len(matrix),len(matrix[0])\n",
    "        l,r = 0,n-1\n",
    "        while l<m and r>=0:\n",
    "            if matrix[l][r]<target:\n",
    "                l+=1\n",
    "            elif matrix[l][r]>target:\n",
    "                r-=1\n",
    "            else:\n",
    "                return True\n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        if not matrix or not matrix[0]:\n",
    "            return False\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        row, col = 0, n - 1\n",
    "        while row < m and col >= 0:\n",
    "            if matrix[row][col] == target:\n",
    "                return True\n",
    "            elif matrix[row][col] > target:\n",
    "                col -= 1\n",
    "            else:\n",
    "                row += 1\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        for line in matrix:\n",
    "            if line:\n",
    "                if line[0] <= target <= line[-1]:\n",
    "                    res = self.search(line, target)\n",
    "                    if res is None:\n",
    "                        continue \n",
    "                    else:\n",
    "                        return True \n",
    "        \n",
    "        return False \n",
    "    \n",
    "    def search(self, arr: List, target) -> bool:\n",
    "        left = 0\n",
    "        right = len(arr) - 1\n",
    "        while left <= right:\n",
    "            mid = (left+right) // 2 \n",
    "\n",
    "            if arr[mid] == target:\n",
    "                return mid\n",
    "            \n",
    "            if arr[mid] < target:\n",
    "                left = mid + 1 \n",
    "            else:\n",
    "                right = mid - 1\n",
    "        \n",
    "        return None \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        for line in matrix:\n",
    "            if line:\n",
    "                if line[0] <= target <= line[-1]:\n",
    "                    res = self.search(line, target)\n",
    "                    if res is None:\n",
    "                        continue \n",
    "                    else:\n",
    "                        return True \n",
    "        \n",
    "        return False \n",
    "    \n",
    "    def search(self, arr: List, target) -> bool:\n",
    "        left = 0\n",
    "        right = len(arr) - 1\n",
    "        while left <= right:\n",
    "            mid = (left+right) // 2 \n",
    "\n",
    "            if arr[mid] == target:\n",
    "                return mid\n",
    "            \n",
    "            if arr[mid] < target:\n",
    "                left = mid + 1 \n",
    "            else:\n",
    "                right = mid - 1\n",
    "        \n",
    "        return None \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        if not matrix or not matrix[0]:\n",
    "            return False\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        x, y = 0, n-1\n",
    "        while True:\n",
    "            if matrix[x][y] == target:\n",
    "                return True\n",
    "            elif matrix[x][y] < target:\n",
    "                if x < m-1:\n",
    "                    x += 1\n",
    "                    continue\n",
    "                else:\n",
    "                    return False\n",
    "            else:\n",
    "                if y > 0:\n",
    "                    y -= 1\n",
    "                    continue\n",
    "                else:\n",
    "                    return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        if not matrix: return False\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        i, j = m-1, 0\n",
    "        while i >= 0 and j < n:\n",
    "            if matrix[i][j] > target:\n",
    "                i -= 1\n",
    "            elif matrix[i][j] < target:\n",
    "                j += 1\n",
    "            else:\n",
    "                return True\n",
    "        return False "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        if not matrix:\n",
    "            return False\n",
    "        row = len(matrix)\n",
    "        column = len(matrix[0])\n",
    "        i, j = 0,  column - 1\n",
    "        while i < row and j >= 0:\n",
    "            if matrix[i][j] == target:\n",
    "                return True\n",
    "            elif matrix[i][j] > target:\n",
    "                j -= 1\n",
    "            else:\n",
    "                i += 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        if not matrix or not matrix[0]:\n",
    "            return False\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        x, y = 0, n-1\n",
    "        while True:\n",
    "            if matrix[x][y] == target:\n",
    "                return True\n",
    "            elif matrix[x][y] < target:\n",
    "                if x < m-1:\n",
    "                    x += 1\n",
    "                    continue\n",
    "                else:\n",
    "                    return False\n",
    "            else:\n",
    "                if y > 0:\n",
    "                    y -= 1\n",
    "                    continue\n",
    "                else:\n",
    "                    return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        if len(matrix) == 0 or len(matrix[0]) == 0:\n",
    "            return False\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        x, y = 0, n - 1\n",
    "        while x < m and y >= 0:\n",
    "            if matrix[x][y] == target:\n",
    "                return True\n",
    "            if matrix[x][y] > target:\n",
    "                y -= 1\n",
    "            else:\n",
    "                x += 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        length = len(matrix)\n",
    "        if length == 0:\n",
    "            return False\n",
    "        height = len(matrix[0])\n",
    "        if height == 0:\n",
    "            return False\n",
    "\n",
    "        if target < matrix[0][0] or target > matrix[length-1][height-1]:\n",
    "            return False\n",
    "\n",
    "        for i in range(length):\n",
    "            if target in matrix[i]:\n",
    "                return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        for line in matrix:\n",
    "            if line:\n",
    "                if line[0] <= target <= line[-1]:\n",
    "                    res = self.search(line, target)\n",
    "                    if res is None:\n",
    "                        continue \n",
    "                    else:\n",
    "                        return True \n",
    "        \n",
    "        return False \n",
    "    \n",
    "    def search(self, arr: List, target) -> int:\n",
    "        left = 0\n",
    "        right = len(arr) - 1\n",
    "        while left <= right:\n",
    "            mid = (left+right) // 2 \n",
    "\n",
    "            if arr[mid] == target:\n",
    "                return mid\n",
    "            \n",
    "            if arr[mid] < target:\n",
    "                left = mid + 1 \n",
    "            else:\n",
    "                right = mid - 1\n",
    "        \n",
    "        return None \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        if len(matrix) == 0 or len(matrix[0]) == 0:\n",
    "            return False\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        x, y = 0, n - 1\n",
    "        while x < m and y >= 0:\n",
    "            if matrix[x][y] == target:\n",
    "                return True\n",
    "            if matrix[x][y] > target:\n",
    "                y -= 1\n",
    "            else:\n",
    "                x += 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        if not len(matrix) or not len(matrix[0]): #特判一下矩阵为空的情况\n",
    "            return False\n",
    "        row = 0\n",
    "        col = len(matrix[0]) - 1\n",
    "        while row != len(matrix) and col != -1:\n",
    "            if matrix[row][col] > target:\n",
    "                col -= 1\n",
    "            elif matrix[row][col] < target:\n",
    "                row += 1   \n",
    "            else:\n",
    "                return True\n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def halfSearch(self, arr: List[int], target: int) -> bool:\n",
    "        left = 0\n",
    "        right = len(arr) - 1\n",
    "        while left <= right:\n",
    "            middle = int((left + right) / 2)\n",
    "            v = arr[middle]\n",
    "            if v < target:\n",
    "                left = middle + 1\n",
    "            elif v > target:\n",
    "                right = middle - 1\n",
    "            else:\n",
    "                return True\n",
    "        return False\n",
    "\n",
    "\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        dim1 = len(matrix)\n",
    "        if dim1 == 0:\n",
    "            return False\n",
    "        for i in range(dim1):\n",
    "            if self.halfSearch(matrix[i], target):\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        # 从右上角开始找，类似二叉排序树\n",
    "        m=len(matrix)\n",
    "        if m==0:\n",
    "            return False\n",
    "\n",
    "        n=len(matrix[0])\n",
    "\n",
    "        pos_x=0\n",
    "        pos_y=n-1\n",
    "        while pos_x<=m-1 and pos_y>=0:\n",
    "            if target==matrix[pos_x][pos_y]:\n",
    "                return True\n",
    "            elif target>matrix[pos_x][pos_y]:\n",
    "                pos_x+=1\n",
    "            else:\n",
    "                pos_y-=1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        if not matrix:\n",
    "            return False\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "        for i in range(m):\n",
    "            l = 0\n",
    "            r = n\n",
    "            while l < r:\n",
    "                mid = (l + r) // 2\n",
    "                if matrix[i][mid] == target:\n",
    "                    return True\n",
    "                elif matrix[i][mid] < target:\n",
    "                    l = mid + 1\n",
    "                else:\n",
    "                    r = mid\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        for i in range(len(matrix)):\n",
    "            if target in matrix[i]:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        m=len(matrix)\n",
    "        if m>0:\n",
    "            n=len(matrix[0])\n",
    "        for row in range(m):\n",
    "            l,r=0,n\n",
    "            while l<r:\n",
    "                # print('col',row,l,r)\n",
    "                mid=(l+r)>>1\n",
    "                if matrix[row][mid]>target:\n",
    "                    r=mid\n",
    "                elif matrix[row][mid]<target:\n",
    "                    l=mid+1\n",
    "                else:\n",
    "                    return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        if len(matrix) == 0 or len(matrix[0]) == 0:\n",
    "            return False\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        x, y = 0, n - 1\n",
    "        while x < m and y >= 0:\n",
    "            if matrix[x][y] == target:\n",
    "                return True\n",
    "            if matrix[x][y] > target:\n",
    "                y -= 1\n",
    "            else:\n",
    "                x += 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        for line in matrix:\n",
    "            if line:\n",
    "                if line[0] <= target <= line[-1]:\n",
    "                    res = self.search(line, target)\n",
    "                    if res is None:\n",
    "                        continue \n",
    "                    else:\n",
    "                        return True \n",
    "        \n",
    "        return False \n",
    "    \n",
    "    def search(self, arr: List, target) -> bool:\n",
    "        left = 0\n",
    "        right = len(arr) - 1\n",
    "        while left <= right:\n",
    "            mid = (left+right) // 2 \n",
    "\n",
    "            if arr[mid] == target:\n",
    "                return mid\n",
    "            \n",
    "            if arr[mid] < target:\n",
    "                left = mid + 1 \n",
    "            else:\n",
    "                right = mid - 1\n",
    "        \n",
    "        return None \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        if not matrix or not matrix[0]:\n",
    "            return False \n",
    "            \n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        res = 0\n",
    "        row = m - 1\n",
    "        col = 0\n",
    "        while row >= 0 and col < n: # 从左下角开始\n",
    "            if matrix[row][col] < target:\n",
    "                col += 1\n",
    "            elif matrix[row][col] > target:\n",
    "                row -= 1\n",
    "            else:\n",
    "                return True                \n",
    "        return False "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        if len(matrix) == 0 or len(matrix[0]) == 0:\n",
    "            return False\n",
    "        for row in matrix:\n",
    "            for element in row:\n",
    "                if element == target:\n",
    "                    return True\n",
    "        return False\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
